package advance.day03;

import java.util.Stack;

/**
 * 描述：
 *      求最大子矩阵
 * @author hl
 * @version 1.0
 * @date 2020/11/6 10:23
 */
public class MaximalRectangle {
    public static void main(String[] args) {
        int[][] map = { { 1, 0, 1, 1 },{ 1, 1, 1, 1 },{ 1, 1, 1, 0 }};
        System.out.println(maxRecSize(map));
    }
    public static int maxRecSize(int[][] map){
        if (map == null || map.length == 0 || map[0].length == 0) {
            return  0;
        }
        int[] bottom = new int[map[0].length];
        int maxArea = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                bottom[j] = map[i][j] == 0 ? 0 : bottom[j] + map[i][j];
            }
            maxArea = Math.max(maxRecAreaFromBottom(bottom), maxArea);
        }
        return maxArea;
    }

    private static int maxRecAreaFromBottom(int[] height) {
        Stack<Integer> stack = new Stack<>();//单调从小到大
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = height[j] * (i - k - 1);
                maxArea = Math.max(maxArea, curArea);
            }
            stack.add(i);
        }
        while(!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = height[j] * (height.length - k - 1);
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }
}
